#_*_coding:utf-8_*_
'''
题目：
    剑指offer 49 丑数

    我们把只包含质因子2,3和5的数称为丑数（Ugly Number)。求按从小到大的顺序的第n个丑数


示例：
    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明：
    1，1是丑数
    2，n 不超过 1690
'''


import collections
from typing import List

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        '''
            丑数只包含因子2,3,5
            因此有丑数 == 某较小丑数 * 某因子

            算法步骤：
                预结算1690个丑数
                    1，初始化数组 dp 和 三个指针 a, b, c
                    2，循环计算所有丑数，每一步：
                        在 dp[a]*2, dp[b]*3, dp[c]*5 选出最小的数字添加到数组 nums中
                        将该数字对应的因子指针向前移动一步
                在数组中返回所需要的丑数。
        '''
        dp, a, b, c = [1]*n, 0, 0, 0
        for i in range(1, n):
            n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
            dp[i] = min(n2, n3, n5)
            if dp[i] == n2:
                a += 1
            if dp[i] == n3:
                b += 1
            if dp[i] == n5:
                c += 1
        return dp[-1]

'''
    最清晰的推导思路：https://leetcode-cn.com/problems/chou-shu-lcof/solution/chou-shu-ii-qing-xi-de-tui-dao-si-lu-by-mrsate/

    此题的解题代码看着很简单。而且使用了动态规划，但是为什么要设置3个指针，并进行相应的+1操作，让我看的很难受
    终于看到大神写的了。

    做笔记如下：
        根据题意，一个丑数必然可以写为 A0*A1*....*A(n-1)*An，其中A属于[2, 3, 5]
        所以 A0*A1*....*A(n-1) 也是一个丑数，说这的意思就是说，一个丑数乘以2,3,5之后
        一定还是一个丑数，并且如果从丑数序列首个元素开始*2*3*5 来计算，丑数序列也不会产生漏解


    假设当前丑数存在三个数组 n2, n3, n5 分别代表丑数序列从1开始分别乘以2,3,5的序列即：
        nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
        nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
        nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
        # 注意 7 不是丑数. 
        # 2, 3, 5 这前 3 个丑数一定要乘以其它的丑数， 所得的结果才是新的丑数， 所以上例中没有出现 7*2, 7*3, 7*5

    那么，最终的愁绪序列实际上就是这3个有序序列对的合并结果，计算丑数序列也就相当于合并3个有序序列

    合并三个有序序列
        最简单的方法就是每一个序列都各自维护一个指针，然后比较指针指向的元素的值，将最小的放入最终
        的合并数组中，并将相应指针向后移动一个元素。

'''
